package 滑动窗口;

import java.util.*;

public class 串联所有单词的子串7 {
    //https://leetcode.cn/problems/substring-with-concatenation-of-all-words/description/
    public static List<Integer> findSubstring1(String s, String[] words) {
        int len = words[0].length()/*, left = 0*/;
        List<Integer> ret = new ArrayList<>();
        HashMap<String,Integer> hashMap_words = new HashMap<>();
        for (String word : words) {
            hashMap_words.put(word, hashMap_words.getOrDefault(word, 0) + 1);
        }
        for (int i = 0; i < len; i++) {
            HashMap<String,Integer> hashMap = new HashMap<>();
            int right = i, left = i;
            int count = 0;
            while (right <= s.length() - len) {
                String tmp = s.substring(right,right + len);
                hashMap.put(tmp,hashMap.getOrDefault(tmp,0) + 1);
                if (hashMap.get(tmp) <= hashMap_words.getOrDefault(tmp,0)) {
                    count++;
                }
                if (right - left > words.length * len - len) {
                    tmp = s.substring(left,left + len);
                    hashMap.put(tmp,hashMap.get(tmp) - 1);
                    if (hashMap.get(tmp) < hashMap_words.getOrDefault(tmp,0)) {
                        count--;
                    }
                    left += len;
                }
                if (count == words.length) {
                    ret.add(left);
                }
                right += len;
            }
        }
        return ret;
    }
    public static List<Integer> findSubstring(String s, String[] words) {
        List<Integer> ret = new LinkedList<>();

        Map<String,Integer> hash1 = new HashMap<>();
        for (String str : words) {
            hash1.put(str,hash1.getOrDefault(str,0) + 1);
        }

        int len = words[0].length(), m = words.length;
        for (int i = 0; i < len; i++) {
            Map<String,Integer> hash2 = new HashMap<>();
            for (int left = i, right = i, count = 0; right + len <= s.length(); right += len) {
                String in = s.substring(right,right + len);
                hash2.put(in,hash2.getOrDefault(in,0) + 1);
                if (hash2.get(in) <= hash1.getOrDefault(in,0)) {
                    count++;
                }
                if (right - left + 1 > len * m) {
                    String out = s.substring(left,left + len);
                    if (hash2.get(out) <= hash1.getOrDefault(out,0)) {
                        count--;
                    }
                    hash2.put(out, hash2.get(out) - 1);
                    left += len;
                }
                if (count == m) {
                    ret.add(left);
                }
            }
        }
        return ret;
    }

    public static void main(String[] args) {
        /*String s = "abc";
        String tmp = s.substring(0,1); // 左闭右开
        System.out.println(tmp); // a*/
        String s = "lingmindraboofooowingdingbarrwingmonkeypoundcake";
        String[] words = new String[] {"fooo","barr","wing","ding","wing"};
        findSubstring(s,words);
    }
}
